// 清北学堂的解法
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 60 + 5;
int a[MAXN], n, M;

vector<int> vec;
vector<int> f[2]; // f[1]: 最后一个元素选的方案, f[0]: 不选的方案

void dfs1(int i, int sm, int las) {
  // 正在考虑第i个选不选，和 mod M=sm，且上一个选还是不选
  if (i == vec.size()) {
    f[las].push_back(sm);
    return;
  }
  // 不选第i 个位置
  dfs1(i + 1, sm, 0);
  // 选第i 个位置，必须有 las==0
  if (las == 0)
    dfs1(i + 1, (sm + vec[i]) % M, 1);
}

long long ans = 0;

int calc(const vector<int> &vec, int val) {
  return upper_bound(vec.begin(), vec.end(), val) -
         lower_bound(vec.begin(), vec.end(), val);
}

void dfs2(int i, int sm, int las) {
  // 正在考虑第i个选不选，和 mod M=sm，且上一个选还是不选
  if (i == vec.size()) {
    // f 种有多少个满足加上 sm 是0
    // f[0] 有多少个 (M-sm)%M
    // + 如果 las=0, f[1] 有多少个 (M-sm)%M

    int val = (M - sm) % M;
    ans += calc(f[0], val);
    if (las == 0)
      ans += calc(f[1], val);
    return;
  }
  // 不选第i 个位置
  dfs2(i + 1, sm, 0);
  // 选第i 个位置，必须有 las==0
  if (las == 0)
    dfs2(i + 1, (sm + vec[i]) % M, 1);
}

int main() {
  scanf("%d%d", &n, &M);
  for (int i = 1; i <= n; ++i)
    scanf("%d", a + i);

  for (int i = 1; i <= (n + 1) / 2; ++i) {
    vec.push_back(a[i]);
  }

  dfs1(0, 0, 0);

  sort(f[0].begin(), f[0].end());
  sort(f[1].begin(), f[1].end());

  vec.clear();
  for (int i = n; i > (n + 1) / 2; --i) {
    vec.push_back(a[i]);
  }

  dfs2(0, 0, 0);

  printf("%lld\n", ans);
  return 0;
}